package com.rimuru.datastructure.binarysearchtree.my;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Binary Search Tree 二叉搜索树
 */
@SuppressWarnings("all")
public class BSTTree1 {


    public BSTNode root;


    public static class BSTNode {
        public int key;
        public Object value;
        public BSTNode left;
        public BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }


        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

    }


    /**
     * <h3>查找关键字对应的值</h3>
     *
     * @param key 关键字
     * @return 关键字对应的值
     */
    public Object get(int key) {

        BSTNode node = root;
        while (node != null) {
            if (node.key < key) {
                node = node.right;
            } else if (node.key > key) {
                node = node.left;
            } else {
                return node.value;
            }

        }
        return null;
    }

    /**
     * <h3>查找最小关键字对应值</h3>
     * 不断向左，直到找到下一个左孩子为空
     *
     * @return 关键字对应的值
     */
    public Object min() {
        return min(root);
    }

    private Object min(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    /**
     * <h3>查找最大关键字对应值</h3>
     * 不断向右，直到找到下一个右孩子为空
     *
     * @return 关键字对应的值
     */
    public Object max() {
        return max(root);
    }

    private Object max(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    /**
     * <h3>存储关键字和对应值</h3>
     * <p>
     * 1. key 有 更新
     * 2. key 没有新增
     *
     * @param key   关键字
     * @param value 值
     */
    public void put(int key, Object value) {
        if (root == null) {
            root = new BSTNode(key, value);
            return;
        }
        BSTNode p = root;
        BSTNode pre = null;
        while (p != null) {
            pre = p;
            if (p.key < key) {
                p = p.right;
            } else if (p.key > key) {
                p = p.left;
            } else {
                // 更新
                p.value = value;
                return;
            }
        }
        // 新增
        if (p == null && pre.key < key) {
            pre.right = new BSTNode(key, value);
            return;
        }
        if (p == null && pre.key > key) {
            pre.left = new BSTNode(key, value);
            return;
        }
    }

    /**
     * <h3>查找关键字的前任值</h3>
     * 1.节点有左子树，此时前驱节点就是左子树的最大值
     * 2.节点没有左子树，若离它最近的、若离它最近的祖先自左而来的，此祖先就是前驱
     * 自左而来,就是父节点向右移动
     *
     * @param key 关键字
     * @return 前任值
     */
    public Object predecessor(int key) {
        BSTNode p = root;
        // 自左而来
        BSTNode ancestorFromLeft = null;
        while (p != null) {
            if (p.key < key) {
                ancestorFromLeft = p;
                p = p.right;
                // 向右找，祖先自左而来
            } else if (p.key > key) {
                p = p.left;

            } else {
                break;
            }
        }
        // 当前节点没找到
        if (p == null) {
            return null;
        }
        // 找到当前节点
        // 1.节点有左子树，此时前驱节点就是左子树的最大值
        if (p.left != null) {
            return max(p.left);
        }
        // 找到当前节点 情况2：节点没有左子树，若离它最近的、自左而来的祖先就是前任
        return ancestorFromLeft != null ? ancestorFromLeft.value : null;
    }

    /**
     * <h3>查找关键字的后任值</h3>
     * <p>
     * 1.节点有右子树，此时后继节点就是右子树的最小值
     * 2.节点没有右子树，若离它最近的、若离它最近的祖先自右而来的，此祖先就是后继
     * 自右而来，就是父节点向左移动
     *
     * @param key 关键字
     * @return 后任值
     */
    public Object successor(int key) {
        BSTNode p = root;
        // 自左而来
        BSTNode ancestorFromRight = null;
        while (p != null) {
            if (p.key < key) {
                p = p.right;
            } else if (p.key > key) {
                ancestorFromRight = p;
                // 向左找，祖先自右而来
                p = p.left;

            } else {
                break;
            }
        }
        // 当前节点没找到
        if (p == null) {
            return null;
        }
        // 找到当前节点
        // 1.节点有右子树，此时后继节点就是右子树的最小值
        if (p.right != null) {
            return min(p.right);
        }
        // 节点没有右子树，若离它最近的、若离它最近的祖先自右而来的，此祖先就是后继
        return ancestorFromRight != null ? ancestorFromRight.value : null;
    }

    /**
     * <h3>根据关键字删除</h3>
     *
     * @param key 关键字
     * @return 被删除关键字对应值
     * <p>
     * 要删除某节点（称为 D），必须先找到被删除节点的父节点，这里称为 Parent
     * <p>
     * 1. 删除节点没有左孩子，将右孩子托孤给 Parent
     * 2. 删除节点没有右孩子，将左孩子托孤给 Parent
     * 3. 删除节点左右孩子都没有，已经被涵盖在情况1、情况2 当中，把 null 托孤给 Parent
     * 4. 删除节点左右孩子都有，可以将它的后继节点（称为 S）托孤给 Parent，设 S 的父亲为 SP，又分两种情况
     * 4.1 SP 就是被删除节点，此时 D 与 S 紧邻，只需将 S 托孤给 Parent
     * 4.2 SP 不是被删除节点，此时 D 与 S 不相邻，此时需要将 S 的后代托孤给 SP，再将 S 托孤给 Parent
     */

    public Object remove(int key) {
        BSTNode p = root;
        BSTNode parent = null;
        while (p != null) {
            if (p.key < key) {
                parent = p;
                p = p.right;
            } else if (p.key > key) {
                parent = p;
                p = p.left;
            } else {
                break;
            }
        }

        if (p.left == null) {
            // 1. 删除节点没有左孩子，将右孩子托孤给 Parent
            // 删除节点左右孩子都没有，已经被涵盖在情况1、情况2 当中，把 null 托孤给 Parent
            shift(parent, p, p.right);
        } else if (p.right == null) {
            // 2. 删除节点没有右孩子，将左孩子托孤给 Parent
            // 删除节点左右孩子都没有，已经被涵盖在情况1、情况2 当中，把 null 托孤给 Parent
            shift(parent, p, p.left);
        } else {
            // p.left !=null  && p.right !=null
            // 4.1 被删除节点找后继,左子树向左走，找最小的值
            BSTNode s = p.right;
            BSTNode sPrarent = p; // 后继节点父亲
            while (s.left != null) {
                sPrarent = s;
                s = s.left;
            }
            // 后继节点即为 s
            if (sPrarent != p) { // 不相邻
                // 4.2 处理后继的后事
                // 后继节点不存在左孩子了
                shift(sPrarent, s, s.right);
                //
                s.right = p.right;
            }
            // 4.3 后继取代被删除节点
            shift(parent, p, s);
            s.left = p.left;

        }
        return p.value;
    }

    /**
     * 托孤方法
     *
     * @param parent  被删除节点的父节点
     * @param deleted 被删除节点
     * @param child   被顶上去的节点
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        if (parent == null) {
            root = child;
            return;
        }
        if (parent.right == deleted) {
            parent.right = child;
            return;
        }
        if (parent.left == deleted) {
            parent.left = child;
            return;
        }
    }


    public Object delete(int key) {
        ArrayList<Object> result = new ArrayList<>(); // 保存被删除节点的值
        root = doDelete(root, key, result);
        return result.isEmpty() ? null : result.get(0);
    }

    /*
                 4
               /   \
              2     6
             / \     \
            1   3     7

            node 起点
            key 待删除关键字
            返回值：删除后的子树
     */
    private BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result) {
        if (node == null) {
            return null;
        }
        if (node.key < key) {
            node.right = doDelete(node.right, key, result);
            return node;
        } else if (node.key > key) {
            node.left = doDelete(node.left, key, result);
            return node;
        }
        result.add(node.value);
        // 情况1 - 只有右孩子
        if (node.left == null) {
            return node.right;
        }
        // 情况2 - 只有左孩子
        if (node.right == null) {
            return node.left;
        }
        // 情况3 - 左右孩子都有 找后继节点
        BSTNode s = node.right;
        BSTNode sPrarent = node; // 后继节点父亲
        while (s.left != null) {
            sPrarent = s;
            s = s.left;
        }
        s.right = doDelete(node.right, s.key, new ArrayList<>());
        s.left = node.left;
        return s;
    }


    // 中序遍历得到升序结果

        /*
                 4
               /   \
              2     6
             / \   / \
            1   3 5   7
     */

    // 找 < key 的所有 value
    public List<Object> less(int key) {
        ArrayList<Object> result = new ArrayList<>();

        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key < key) {
                    result.add(pop.value);
                } else {
                    break;
                }
                p = pop.right;

            }
        }
        return result;
    }

//    // 找 > key 的所有 value
//    public List<Object> greater(int key) {
//        ArrayList<Object> result = new ArrayList<>();
//
//        BSTNode p = root;
//        LinkedList<BSTNode> stack = new LinkedList<>();
//        while (p != null || !stack.isEmpty()) {
//            if (p != null) {
//                stack.push(p);
//                p = p.left;
//            } else {
//                BSTNode pop = stack.pop();
//                if (pop.key > key) {
//                    result.add(pop.value);
//                }
//                p = pop.right;
//            }
//        }
//        return result;
//    }

    // 找 > key 的所有 value 反向中序遍历
    public List<Object> greater(int key) {
        ArrayList<Object> result = new ArrayList<>();

        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.right;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                }else {
                    break;
                }
                p = pop.left;
            }
        }
        return result;
    }

    // 找 >= key1 且 <= key2 的所有值
    public List<Object> between(int key1, int key2) {
        ArrayList<Object> result = new ArrayList<>();

        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key >= key1 && pop.key <= key2) {
                    result.add(pop.value);
                }else if (pop.key > key2) {
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        BSTTree1 tree = new BSTTree1();
    }
}






